

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

A Backtracking Solver for CSPs

Utility Functions

The module extractVariables implements the function $\texttt{extractVars}(e)$ that takes a Python expression $e$ as its argument and returns the set of all variables and function names occurring in $e$.



In [ ]:

    
import extractVariables as ev

The function collect_variables(expr) takes a string expr that can be interpreted as a Python expression as input and collects all variables occurring in expr. It takes care to eliminate the function symbols from the names returned by extract_variables.



In [ ]:

    
def collect_variables(expr):
    return { var for var in ev.extractVars(expr)
                 if  var not in dir(__builtins__)
           }



In [ ]:

    
ev.extractVars('abs(x - y) + abs(z1 - z2)')



In [ ]:

    
collect_variables('abs(x - y) + abs(z1 - z2)')

The function arb(S) takes a set S as input and returns an arbitrary element from this set.



In [ ]:

    
def arb(S):
    "Return some element from the set S."
    for x in S:
        return x

Backtracking is simulated by raising the Backtrack exception. We define this new class of exceptions so that we can distinguish Backtrack exceptions from ordinary exceptions. This is done by creating a new, empty class that is derived from the class Exception.



In [ ]:

    
class Backtrack(Exception):
    pass

The Backtracking Solver

The procedure solve(P) takes a a constraint satisfaction problem P as input. Here P is a triple of the form $$ \mathcal{P} = \langle \mathtt{Variables}, \mathtt{Values}, \mathtt{Constraints} \rangle $$ where

$\mathtt{Variables}$ is a set of strings which serve as variables,
$\mathtt{Values}$ is a set of values that can be assigned to the variables in the set $\mathtt{Variables}$.
$\mathtt{Constraints}$ is a set of formulas from first order logic.
Each of these formulas is called a constraint of $\mathcal{P}$.

The main purpose of the function solve is to convert the CSP P into an augmented CSP where every constraint $f$ is annotated with the variables ocurring in $f$. This annotates CSP is then solved using backtrack_search.



In [ ]:

    
def solve(P):
    Variables, Values, Constraints = P
    csp = (Variables, Values, [(f, collect_variables(f)) for f in Constraints])
    try:
        return backtrack_search({}, csp)
    except Backtrack:
        return None

The function backtrack_search takes two arguments:

Assignment is a partial variable assignment that is represented as a dictionary. Initially, this assignment will be the empty dictionary. Every recursive call of backtrack_search adds the assignment of one variable to the given assignment.
P is an augmented constraint satisfaction problem, i.e. P is a tripple of the form $$ \mathcal{P} = \langle \mathtt{Vars}, \mathtt{Values}, \mathtt{Constraints} \rangle $$ where
- $\mathtt{Vars}$ is a set of strings which serve as variables,
- $\mathtt{Values}$ is a set of values that can be assigned to the variables in $\mathtt{Vars}$.
- $\mathtt{Constraints}$ is a set of pairs of the form $(f, V)$ where $f$ is a Boolean Python expression, while $V$ is the set of variables occuring in $f$. The function backtrack_search tries to find a solution of P by recursively augmenting Assignment.



In [ ]:

    
def backtrack_search(Assignment, P):
    print(Assignment) # useful to observe backtracking in action
    Variables, Values, Constraints = P
    if len(Assignment) == len(Variables):
        return Assignment
    var = arb(Variables - Assignment.keys())
    for value in Values:
        try:
            if is_consistent(var, value, Assignment, Constraints):
                NewAss = Assignment.copy()
                NewAss[var] = value
                return backtrack_search(NewAss, P)
        except Backtrack:
            continue
    raise Backtrack()

The function $\texttt{is_consistent}(\texttt{var}, \texttt{value}, \texttt{Assignment}, \texttt{csp})$ takes four arguments:

$\texttt{var}$ is a variable that does not occur in $\texttt{Assignment}$,
$\texttt{value}$ is a value that can be substituted for this variable,
$\texttt{Assignment}$ is a consistent partial variable assignment. A partial variable assignment $A$ is consistent if all constraints $f$ that contain only variables from the set $\mathtt{dom}(A)$ are satisfied.
$\texttt{csp}$ is an augmented constraint satisfaction problem.

This function returns True iff the partial variable assignment $$\texttt{Assignment} \cup \{\langle\texttt{var} \mapsto\texttt{value}\rangle\}$$ is consistent with all the constraints occurring in $\texttt{csp}$.



In [ ]:

    
def is_consistent(var, value, Assignment, Constraints):
    NewAssign      = Assignment.copy()
    NewAssign[var] = value
    return all(eval(f, NewAssign) for (f, Vs) in Constraints
                                  if  var in Vs and Vs <= NewAssign.keys()
              )

Solving the Eight-Queens-Puzzle



In [ ]:

    
%run N-Queens-Problem-CSP.ipynb



In [ ]:

    
P = create_csp(8)

Backtracking search takes about 15 milliseconds on my desktop to solve the eight queens puzzle.



In [ ]:

    
%%time
Solution = solve(P)
print(f'Solution = {Solution}')



In [ ]:

    
show_solution(Solution)

Solving the Zebra Puzzle



In [ ]:

    
%run Zebra.ipynb



In [ ]:

    
zebra = zebra_csp()

Backtracking takes about 1 minute and 7 seconds to solve the Zebra Puzzle.



In [ ]:

    
%%time
Solution = solve(zebra)



In [ ]:

    
show_solution(Solution)



In [ ]: